Bitcoin Red-Bulled: Batch Verification's Arrival

Batch verification is a technique to validate multiple digital signatures simultaneously, outpacing the speed of traditional individual verification methods. If you're intrigued, keep reading....

As part of the Summer of Bitcoin 2022 program, I've been focusing on developing the Schnorr Batch Verification Interface for libsecp256k1, a C library used by Bitcoin. In this blog post, I'll give you a quick rundown of batch verification and share a glimpse of the work I've been doing.

But before we dive in:

Q: Ever wondered how Bitcoin makes sure a transaction is legit?

Understanding this will provide us with the necessary foundation to see how the concept of "batch verification" integrates into the intricate system of Bitcoin.

Transaction Validation

Every transaction contains a script inside it. These scripts are written in a stack-based programming language called Script. After executing such a script, if the stack is empty, or has a non-zero value, or has True on top, then Bitcoin considers the transaction valid. For example, Bitcoin core checks these script conditions using the EvalScript() function.

The essence of a script inside a transaction (aka ScriptSig) is to prove the ownership of bitcoins. Hence, most scripts (like P2PK, P2PKH) contain a digital signature inside them. The Bitcoin Script language provides the OP_CHECKSIG opcode to verify such signatures.

Note: It is not necessary for a script to have a digital signature inside it. P2SH scripts are a great example of this.

Single Verification

At the time of writing, the OP_CHECKSIG supports two different types of digital signature verification (using EvalChecksig).

1. ECDSA signature verification - by EvalChecksigPreTapscript

2. Schnorr signature verification - by EvalChecksigTapscript

Not too long ago, Bitcoin core used to support only ECDSA signatures. The Schnorr signatures were introduced to Bitcoin in its most recent update called Taproot (activated in Nov 2021). If you look at this commit, you can observe that it modifies the EvalChecksig to support Schnorr signature verification.

Tip: use `git blame` to find the commit that added a particular line to a codebase

Q: Why go through the pain of adding a new signature type if "Bitcoin already works"?

The rationale lies in the potential payoff. Incorporating the Schnorr signature into Bitcoin doesn't just tinker at the edges—it unlocks fresh opportunities like Batch Verification, MuSig, Scriptless Script, FROST, and more!

If you want to learn more about the Schnorr signatures, this blog series is the best place to start.

Batch Verification

Batch verification is a method to verify many digital signatures at once. This is more efficient than verifying signatures one by one. So, introducing such a method to Bitcoin will significantly speed up block validation and initial block download.

Q: Why is batch verification faster than single verification? Don't we have equal elliptic curve multiplications in both cases?

The speed boost in batch verification arises from the method employed for multi-scalar multiplication. Unlike the straightforward approach of individual point multiplication followed by addition, using specialized techniques like the Strauss and Pippenger algorithms delivers a significant speed boost.

Take libsecp256k1, for instance—there's an ecmult_multi_simple_var fn, which executes the basic point multiplication followed by addition (a naive approach). On the other hand, it also supports ecmult_strauss_batch and ecmult_pippenger_batch, which leverages advanced multi-scalar point multiplication techniques.

The YT video below dives deeper into the math behind these algorithms and why they offer such speed-ups.

Project Summary

libsecp256k1

To introduce batch verification to Bitcoin Core, we first need to implement the necessary cryptographic functions in libsecp256k1, a C library used by Bitcoin Core for low-level elliptic curve operations. Initially, libsecp256k1 started out as a personal project of Pieter Wuille, which was later integrated into Bitcoin Core. You can listen to this Chaincode podcast below, where he talks about its early developments.

History

There is already a pull request (PR #760) that implements a batch verification for BIP340 Schnorr signatures on libsecp. However, the API proposed in that pull request was restricted in a sense because it only allowed batch verifying Schnorr signatures.

Recognizing the need for a more versatile solution, the developers aspired to create a comprehensive set of APIs. These APIs were designed not only to facilitate batch verification of Schnorr signatures but also to encompass Taproot commitments, a crucial component utilized in script-path spending scenarios. As a result, they put forth this project idea to the Summer of Bitcoin program

Proposal Round

Having reviewed the project idea on the SoB website, I started investigating the different ways to implement these batch APIs and wrote a detailed project proposal with my findings. You can find the proposal here. It also comes with a proof of concept code.

For anyone considering applying to SoB, I strongly recommend including a proof of concept code in your project proposal, as it can significantly enhance your likelihood of being accepted into the program.

Implementation Details

The requirement here is to provide the user with a black box where they can add their inputs. Once completed, the black box will tell whether the inputs are valid or invalid.

For the user to carry out actions, such as creating a black box and adding input, we must establish an interface that grants access to the black box. This interface is referred to as the batch verification interface, which is quite self-explanatory.

The batch verification interface consists of the following APIs:

1. batch_create - creates a batch object

2. batch_usable - checks if the batch object can be used by batch_add_* APIs

3. batch_add_schnorrsig - adds a Schnorr signature to the batch

4. batch_add_tweak_check - adds a tweaked pubkey check to the batch

5. batch_verify - succeeds if and only if sigs & tweak checks in batch are valid

6. batch_destroy - destroys the batch object

You can find the pull request implementing the above APIs here. I have also presented my project in one of libsecp's developer meetings.

Note: The above APIs are simple C functions which a user could use in their program after linking it with the libsecp256k1 library

Usage Example

An example C program demonstrating the recommended usage for the batch APIs.

You can find a more detailed C code (using these APIs) here.

Performance

In my introduction to batch verification, I highlighted its superior speed compared to regular verification. However, it's essential to address the practical implications: just how substantial is the speed enhancement achieved by these batch APIs, and how do we precisely quantify it?

Fortunately, libsecp256k1 provides a dedicated benchmark function called run_benchmark, designed to measure the execution time of specific functions. Leveraging this tool, I conducted benchmarks on the batch APIs, yielding the following results:

1. Batch verifying Schnorr Signatures is 20% faster than single verification.

2. Batch verifying tweaked pubkey checks is 50% faster than single verification.

I have also visualized the benchmarks on a semi-log graph using the GNU plot software.

Schnorr Signature speed-up

Tweak check speed-up

Further Improvements

Presently, the existing batch verification implementation is 20 to 50 percent faster than single verification. While this might appear promising, it's important to recognize that we're just scratching the surface of its true potential. What truly sets batch verification apart is its capacity for speed-up that escalates with an increasing number of signatures (see this graph). This stands in stark contrast to the current implementation, where the speed-up plateaus after reaching a certain quantity of signatures.

The current implementation encounters a speed-up plateau due to its exclusive reliance on the Strauss algorithm for computing multi-scalar multiplication. This limitation represents a notable caveat within the project. An optimal batch verification implementation would ideally incorporate a strategic shift to the Pippenger algorithm beyond a certain threshold of signatures.

We chose not to switch due to the seamless fit between the existing batch APIs and libsecp256k1's internal Strauss batch APIs. This alignment required minimal changes, unlike Pippenger integration. However, we have the option to internally modify the current batch_verify APIs to support a potential switch to Pippenger without impacting user-facing APIs. This offers a promising avenue for future enhancements.

Closing Note

The Summer of Bitcoin ended a few weeks ago, which doesn't mean I will stop working on my project. For the next few months, I will update the PR according to the suggestion from the libsecp's maintainers.

I'm truly grateful to have had the chance to work on the batch verification project, and I consider myself lucky to have had Jonas Nick as my mentor. His guidance and assistance have been absolutely essential in bringing this project to life. I also want to extend my thanks to Adi Shankara and the Summer of Bitcoin program for providing me with this incredible opportunity. This experience has been invaluable in my growth and learning journey.

If you are a university student interested in Bitcoin, I highly recommend you apply for this program. SoB can be a life-changing experience if used properly. If you have any questions, feel free to contact me at siv2ram@gmail.com, siv2r (Twitter), or sivaram (LinkedIn).